#include<iostream>
#include<vector>
#include<deque>
#include<string>
#include<algorithm>
#include<unordered_set>
using namespace std;


struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x), left(nullptr), right(nullptr){}
};

class Solution{
    private:
    deque<TreeNode*> Node;
    vector<vector<int>> val;

    public:
    vector<vector<int>> ans1(TreeNode* root){
        if(root == nullptr){
            return val;
        }

        Node.push_back(root);
        deque<int> temp;
        int layer = 0;
        while(!Node.empty()){
            int i = Node.size();
            while(i > 0){
                TreeNode* node = Node.front();
                Node.pop_front();
                if(node->left){
                    Node.push_back(node->left);
                }
                if(node->right){
                    Node.push_back(node->right);
                }
                if(layer % 2 == 0){
                    temp.push_back(node->val);
                }else{
                    temp.push_front(node->val);
                }
                i--;
            }
            layer++;
            val.emplace_back(vector<int>{temp.begin(), temp.end()});
            temp.clear();
        }

        return val;
    }

};

TreeNode* createTree(vector<int>& num, int index, int len){
    if(num[index] == '#'){
        return NULL;
    }
    TreeNode* root = new TreeNode(num[index]);

    if(index * 2 + 1 < len){
        root->left = createTree(num, index * 2 + 1, len);
    }else{
        root->left = nullptr;
    }
    if(index * 2 + 2 < len){
        root->right = createTree(num, index * 2 + 2, len);
    }else{
        root->right = nullptr;
    }

    return root;
}

void show(vector<vector<int>>& num){
    int len = num.size();
    for(int i = 0; i != len; i++){
        int sublen = num[i].size();
        for(int j = 0; j != sublen-1; j++){
            cout << num[i][j] << " " << ends;
        }
        cout << num[i][sublen-1] << endl;
    }
}

void test1(){
    vector<int> num = {3,9,20,'#','#',15,7};
    TreeNode* root = createTree(num, 0, num.size());

    Solution s;
    vector<vector<int>> ret = s.ans1(root);
    show(ret);
    
}

void test2(){
    vector<int> num = {1};
    TreeNode* root = createTree(num, 0, num.size());

    Solution s;
    vector<vector<int>> ret = s.ans1(root);
    show(ret);
    
}

void test3(){
    vector<int> num = {1,2,3,4,'#','#',5};
    TreeNode* root = createTree(num, 0, num.size());

    Solution s;
    vector<vector<int>> ret = s.ans1(root);
    show(ret);
    
}


int main(void){
    test1();
    cout << "-----------------------------" << endl;
    test2();
    cout << "-----------------------------" << endl;
    test3();

    return 0;
}